package demo2;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * 归并排序        √
 * 归并排序非递归   √
 * 归并排序小和问题  √
 * 逆序对问题      √
 * 大于2倍问题     √
 * 区间和问题      √
 * 对链表进行归并排序
 * User: 石方旭
 * Date: 2022-07-08
 * Time: 9:16
 */
public class TestMergeSort {


    /**
     * 给定一个数组arr，两个整数lower和upper，
     * 返回arr中有多少个子数组的累加和在[lower,upper]范围上
     */


    public static int merge(int[] sum, int left,int mid, int right, int lower, int upper) {
        int b1 = left;
        int b2 = mid+1;
        int ans = 0;
        int[] tmp = new int[right-left+1];
        int k =0;
        int windowL = left;
        int windowR = left;
        for(int i = mid+1;i<=right;++i){
            int max = sum[i] - lower;
            int min = sum[i] - upper;
            while(windowR<=mid&&sum[windowR]<=max){
                windowR++;
            }
            while(windowL<=mid&&sum[windowL]<min){
                windowL++;
            }
            ans += windowR - windowL;
        }

        while(b1<=mid&&b2<=right){
            ans += sum[b1]<sum[b2]?sum[b1]*(right-b2+1):0;
            tmp[k++] = sum[b1]< sum[b2]? sum[b1++] :sum[b2++];
        }
        while(b1<=mid){
            tmp[k++] = sum[b1++];
        }
        while(b2<=right){
            tmp[k++] = sum[b2++];
        }
        //拷贝会原来的数组
        for(int i = 0;i<tmp.length;++i){
            sum[left+i] = tmp[i];
        }
        return ans;
    }


    public static int process(int[] sum, int L, int R, int lower, int upper) {
        if (L == R) {
            if (sum[L] >= lower && sum[R] <= upper) {
                return 1;
            } else {
                return 0;
            }
        }
        int mid = L + ((R - L) >>> 1);
        int leftPart = process(sum, L, mid, lower, upper);
        int rightPart = process(sum, mid + 1, R, lower, upper);
        int merge = merge(sum, L,mid, R, lower, upper);
        return leftPart + rightPart + merge;
    }

    public static int countRangeSum(int[] array, int lower, int upper) {
        int[] sum = new int[array.length];
        sum[0] = array[0];
        for (int i = 1; i < array.length; ++i) {
            sum[i] = sum[i - 1] + array[i];
        }
        return process(sum, 0, sum.length - 1, lower, upper);

    }

    /**
     * nums = [-2,5,-1], lower = -2, upper = 2
     * ans = 3
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {-2, 5, -1};
        int lower = -2;
        int upper = 2;
        int ret = countRangeSum(arr, lower, upper);

    }
}


/**
 * 在一个数组中，一个数左边比它小的数的总和，叫该数的小和 所有数的小和累加起来，叫数组小和
 * 例子： [1,3,4,2,5] 1左边比1小的数：没有 3左边比3小的数：1 4左边比4小的数：
 * 1、3 2左边比2小的数：1 5左边比5小的数：1、3、4、 2
 * 所以数组的小和为1+1+3+1+1+3+4+2=16 给定一个数组arr，求数组小和
 */

/**
 * 在一个数组中，任何一个前面的数a，和任何一个后面的数b，
 * 如果(a,b)是降序的，就称为降序对 给定一个数组arr，求数组的降序对总数量
 */

/**
 * 在一个数组中，对于任何一个数num，求有多少个(后面的数*2)依然<num,返回总个数
 * 比如：[3,1,7,0,2] 3的后面有：1，0
 * 1的后面有：0 7的后面有：0，2
 * 0的后面没有 2的后面没有 所以总共有5个
 */
//public static int merge(int[] array,int left,int mid,int right){
//    int b1 = left;
//    int e1 = mid;
//    int b2 = mid+1;
//    int e2 = right;
//    int windowR = mid +1;
//    int ans = 0;
//    for(int i = left;i<=mid;++i){
//        if(windowR<=right&&array[i]>2*array[windowR]){
//            windowR++;
//        }
//        ans += windowR-mid-1;
//    }
//    int[] tmp = new int[right-left+1];
//    int k =  0;
//    while(b1<=e1&&b2<=e2){
//
//        tmp[k++] = array[b1]<=array[b2]? array[b1++]:array[b2++];
//    }
//    while(b1<=e1){
//        tmp[k++] = array[b1++];
//    }
//    while(b2<=e2){
//        tmp[k++] = array[b2++];
//    }
//    //拷贝会原来的数组
//    for(int i = 0;i<tmp.length;++i){
//        array[left+i] = tmp[i];
//    }
//    return ans;
//
//}
//
//
//    public static int process1(int[] array,int left,int right){
//        if(left>=right) return 0;
//        int mid = left + ((right-left)>>>1);
//        return process1(array, left, mid) + process1(array, mid+1, right)
//                + merge(array,left,mid,right);
//    }
//
//    public static int twoNum(int[] array){
//        if(array==null||array.length<2){
//            return 0;
//        }
//        return process1(array,0,array.length-1);
//    }
//
//    public static void main(String[] args) {
//        int[] array = {3,1,7,0,2};
//        int ret = twoNum(array);
//        System.out.println(ret);
//    }
//
//
//public static int merge1(int[] array,int left,int mid,int right){
//    int b1 = mid;
//    int b2 = right;
//    int e2 = mid+1;
//    int ans = 0;
//    int[] tmp = new int[right-left+1];
//    int k = tmp.length - 1;
//    while(b1>=left && b2>=mid+1){
//        ans += array[b1]>array[b2] ? (b2-e2+1):0;
//        tmp[k--] = array[b1]>array[b2]?array[b1--]:array[b2--];
//    }
//    while(b1>=left){
//        tmp[k--] = array[b1--];
//    }
//    while(b2>=mid+1){
//        tmp[k--] = array[b2--];
//    }
//    //拷贝会原来的数组
//    for(int i = 0;i<tmp.length;++i){
//        array[left+i] = tmp[i];
//    }
//    return ans;
//}
//
//    public static int process1(int[] array,int left,int right){
//        if(left>=right) return 0;
//        int mid = left + ((right-left)>>>1);
//        return process1(array, left, mid) + process1(array, mid+1, right)
//                + merge1(array,left,mid,right);
//    }
//
//    public static int reversePairs(int[] array){
//        if(array==null||array.length<2){
//            return 0;
//        }
//        return process1(array,0,array.length-1);
//    }



//    public static int merge1(int[] array,int left,int mid,int right){
//        int b1 = left;
//        int b2 = mid+1;
//        int ans = 0;
//        int[] tmp = new int[right-left+1];
//        int k =0;
//        while(b1<=mid&&b2<=right){
//            ans += array[b1]<array[b2]?array[b1]*(right-b2+1):0;
//            tmp[k++] = array[b1]< array[b2]? array[b1++] :array[b2++];
//        }
//        while(b1<=mid){
//            tmp[k++] = array[b1++];
//        }
//        while(b2<=right){
//            tmp[k++] = array[b2++];
//        }
//        //拷贝会原来的数组
//        for(int i = 0;i<tmp.length;++i){
//            array[left+i] = tmp[i];
//        }
//        return ans;
//    }
//
//    public static int process1(int[] array,int left,int right){
//        if(left>=right) return 0;
//        int mid = left + ((right-left)>>>1);
//        return process1(array, left, mid) + process1(array, mid+1, right)
//                + merge1(array,left,mid,right);
//    }
//
//    public static int smallSum(int[] array){
//        if(array==null||array.length<2){
//            return 0;
//        }
//        return process1(array,0,array.length-1);
//    }

//    public static void merge(int[] array,int left,int mid,int right){
//        int b1 = left;
//        int e1 = mid;
//        int b2 = mid+1;
//        int e2 = right;
//        int[] tmp = new int[right-left+1];
//        int k =  0;
//        while(b1<=e1&&b2<=e2){
//            tmp[k++] = array[b1]<=array[b2]? array[b1++]:array[b2++];
//        }
//        while(b1<=e1){
//            tmp[k++] = array[b1++];
//        }
//        while(b2<=e2){
//            tmp[k++] = array[b2++];
//        }
//        //拷贝会原来的数组
//        for(int i = 0;i<tmp.length;++i){
//            array[left+i] = tmp[i];
//        }
//
//    }
//
//    public static void process(int[] array,int left,int right){
//        if(left>=right) return ;
//        int mid = left + ((right - left)>>>1);
//        process(array,left,mid);//左半部分有序
//        process(array,mid+1,right);//右半部分有序
//        //开始归并
//        merge(array,left,mid,right);
//    }
//
//    //普通归并排序
//    public static void mergeSort(int[] array){
//        if(array==null||array.length<2){
//            return ;
//        }
//         process(array,0,array.length-1);
//    }
//
//    public static void mergeNor(int[] array){
//        int left = 0;
//        int right = array.length;;
//        int mid = left + ((right - left)>>>1);
//         int gap = 1;
//         // 1 2 3 4
//         while(gap<array.length){
//             for(int i = 0;i<array.length;i+=2*gap){
//                  left = i;
//
//                  mid = left + gap -1;
//                  if(mid>=array.length){
//                     mid = array.length-1;
//                  }
//                  right = mid+ gap;
//                  if(right>=array.length){
//                     right = array.length-1;
//                  }
//                  merge(array,left,mid,right);
//             }
//             gap*=2;
//         }
//    }
//}
